UVa/11003 - Boxes/11003.cpp

   1 /*
   2   Time limit exceeded.
   3  */
   4 #include <iostream>
   5 #include <algorithm>
   6
   7 using namespace std;
   8
   9 const int maxBoxes = 1000;
  10 const int maxLoad = 3000;
  11 int dp[maxBoxes][maxLoad+1];
  12 /*
  13   dp[i][j] = Máxima cantidad de cajas que puedo apilar
  14   tal que la caja i-ésima esté encima y que pueda montar
  15   otros j kilos arriba.
  16 */
  17 int w[maxBoxes], l[maxBoxes];
  18
  19 int main(){
  20   int n;
  21   while (cin >> n && n){
  22
  23     for (int i=0; i<n; ++i)
  24       for (int j=0; j<=maxLoad; ++j)
  25         dp[i][j] = 0;
  26
  27
  28     int answer = -1;
  29     for (int i=0; i<n; ++i){
  30       cin >> w[i] >> l[i];
  31       for (int j=0; j<= l[i]; ++j){
  32         dp[i][j] = 1;
  33         if (j + w[i] <= maxLoad){
  34           for (int k=0; k<i; ++k){
  35             dp[i][j] = std::max(dp[i][j], dp[k][j+w[i]] + 1);
  36           }
  37         }
  38       }
  39       answer = std::max(answer, dp[i][0]);
  40     }
  41     cout << answer << endl;
  42   }
  43   return 0;
  44 }